package Search;

import java.util.ArrayList;
import java.util.List;

/*
二分查找
 */
public class BinarySearch {

  public static void main(String[] args) {
    int[] arr = new int[]{1,8,10,89,1000,1000,1000,1234};
    int index = binarySearch(arr, 0, arr.length - 1, 1000);
    if (index == -1) {
      System.out.println("没有找到该数");
    } else {
      System.out.println("该数得下标为" + index);
    }

    ArrayList<Integer> list = binarySearch2(arr, 0, arr.length, 1000);
    System.out.println(list);

  }

  public static int binarySearch(int[] arr, int left, int right, int findVal) {

    System.out.println("count");
//    说明递归完了数组，没找到
    if (left > right) {
      return -1;
    }

    int mid = (left + right) / 2;
    int midVal = arr[mid];
    if (findVal > midVal) {
      return binarySearch(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {
      return binarySearch(arr, left, right - 1, findVal);
    } else {
      return mid;
    }
  }
  /*
  思路分析
  1.在找到mid索引值,不要马上返回
  2.向mid素引值的左边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList3。
    向mid索引值的右边扫描，将所有满足1000，的元素的下标，加入到集合ArrayList4。
    将Arraylist返回
   */
  public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {

    System.out.println("count");
//    说明递归完了数组，没找到
    if (left > right) {
      return new ArrayList<Integer>();
    }

    int mid = (left + right) / 2;
    int midVal = arr[mid];
    if (findVal > midVal) {
      return binarySearch2(arr, mid + 1, right, findVal);
    } else if (findVal < midVal) {
      return binarySearch2(arr, left, right - 1, findVal);
    } else {
      ArrayList<Integer> list = new ArrayList<Integer>();
//      向左查找
      int temp = mid - 1;
      while (true){
        if (temp < 0 || arr[temp] != findVal){
          break;
        }
        list.add(temp);
        temp--;
      }
      list.add(mid);

//      向右查找
      temp = mid + 1;
      while (true){
        if (temp > arr.length - 1 || arr[temp] != findVal){
          break;
        }
        list.add(temp);
        temp++;
      }
      return list;
    }
  }
}
